package com.gaogzhen.datastructure.symbolTable;

/**
 * 有序符号表接口
 * @author Administrator
 * @version 1.0
 * @description
 * @date 2022-11-11 21:13
 */
public interface SortedST<K, V> extends ST<K, V>{
    /**
     * 最小键
     * @return  最小键
     */
    K min();

    /**
     * 最大键
     * @return  最大键
     */
    K max();

    /**
     * 向下取整，返回小于等于指定键的最大键
     * @param key   目标键
     * @return      小于等于指定键的最大键
     */
    K floor(K key);

    /**
     * 向上取整，返回大于等于目标键的最小键
     * @param key   目标键
     * @return  大于等于目标键的最小键
     */
    K ceiling(K key);

    /**
     * 小于key的键值对数量
     * @param key    目标key
     * @return      小于key的键值对数量
     */
    int rank(K key);

    /**
     * 排名为K的键
     * @param k 排名
     * @return  排名K对应的键
     */
    K select(int k);

    /**
     *
     * @param index
     * @return
     */
    V delete(int index);

    /**
     * 删除最小键对应的键值对
     * @return  最小键对应的值
     */
    V deleteMin();

    /**
     * 删除最大键对应的键值对
     * @return  最大键对应的值
     */
    V deleteMax();

    /**
     * 范围内键值对数量
     * @param lo    范围下限
     * @param hi    范围上限
     * @return      范围内键值对数量
     */
    int size(K lo, K hi);

    /**
     * 范围内键的集合
     * @param lo    范围下限
     * @param hi    范围上限
     * @return      范围内键的集合
     */
    Iterable<K> keys(K lo, K hi);
}
